%%%-------------------------------------------------------------------
%%% File    : p32.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% We shall say that an n-digit number is pandigital if it makes use 
%%% of all the digits 1 to n exactly once; for example, the 5-digit 
%%% number, 15234, is 1 through 5 pandigitial.
%%%
%%% The product 7254 is unusual, as the identity, 39 × 186 = 7254, 
%%% containing multiplicand, multiplier, and product is 1 through 
%%% 9 pandigital.
%%%
%%% Find the sum of all products whose multiplicand/multiplier/product 
%%% identity can be written as a 1 through 9 pandigital.
%%% HINT: Some products can be obtained in more than one way so be sure 
%%% to only include it once in your sum.
%%%
%%% Created : 25 Dec 2008
%%%-------------------------------------------------------------------
-module(p32).

%% API
-compile(export_all).

% The only options for the multiplicand/multiplier are:
% 1 digit * 4 digit = 4 digit 
% 2 digit * 3 digit = 4 digit
% These are the only combinations where multiplicant, multiplier and
% product have 9 digits in total
% Additionally for a fixed multiplier M1 the multiplicand is limited by
% (1) 9999 div M1.
% The solution is to run through all permutations of the digits 1-9 of
% size 1 and 2, for each one using the digits not already in use
% generate the permutations of size respectively 4 or 3 and test the 
% products if they are bellow the limit (1 above). 


%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution()->
    AllDigits = lists:seq(1, 9),
    Tbl = ets:new(tbl, []),
    %first find all that are product of 
    Fun1 = fun(N, Acc) ->
                   test(N, 4, lists:delete(N, AllDigits), 8, 0, count(8, 4), max_mult(N), Tbl, Acc)
           end,
    Products1 = lists:foldr(Fun1, [], AllDigits),
    Max1 = count(9, 2),
    Max2 = count(7, 3),
    Fun2 = fun(I1, Acc, _)when I1 >= Max1 ->
                   Acc;
              (I1, Acc, Funself) ->
                   {M1, Rest} = nth_permutation(I1, 9, 2, AllDigits),
                   Funself(I1 + 1, test(M1, 3, Rest, 7, 0, Max2, max_mult(M1), Tbl, Acc), Funself)
           end,
    Products = Fun2(0, Products1, Fun2),
    lists:sum(Products).

%%====================================================================
%% Internal functions
%%====================================================================
%
% For a fixed multiplicand M1, iterates through all possible multipliers
% and collects them if the multiplicand, the multiplier and the product 
% form a pandigital number
test(_, _, _, _, MaxI, MaxI, _, _, Acc) -> Acc;
test(M1, Size, Digits, DigitsCount, I, MaxI, MaxM2, Tbl, Acc) ->
    {M2, Rest} = nth_permutation(I, DigitsCount, Size, Digits),
    case M2 > MaxM2 of
        true ->
            test(M1, Size, Digits, DigitsCount, I + 1, MaxI, MaxM2,Tbl, Acc);
        _ -> Product = M1*M2,
             Exists = ets:lookup(Tbl, Product),
             case Exists of 
                 [] ->
                     PDigits = lists:sort(number_to_digits(Product)),
                     %the triplet is pandigital if the product contains the same digit as
                     %the list of the digits unused by the 2 multipliers.
                     NewAcc = case PDigits =:= Rest of 
                                  true -> 
                                      ets:insert(Tbl, {Product, true}),
                                      [Product|Acc];
                                  _ ->
                                      Acc
                              end,
                     test(M1, Size, Digits, DigitsCount, I + 1, MaxI, MaxM2, Tbl, NewAcc);
                 _ -> test(M1, Size, Digits, DigitsCount, I + 1, MaxI, MaxM2, Tbl, Acc)
             end
    end.
                     
%The maximum multiplier for a given multiplicand.
max_mult(X) when X < 100 ->
    9999 div X.    

%How many possible permutations of DigitsCount digits of size Size.
count(DigitsCount, Size)->
    count(DigitsCount, Size, 1).
count(_, 0, Acc) ->
    Acc;
count(DigitsCount, Size, Acc) ->
    count(DigitsCount - 1, Size - 1, DigitsCount*Acc).

%Generate the Index-th permutation of size Size from DigitsCount digits.
nth_permutation(Index, DigitsCount, Size, Digits) ->
    nth_permutation(Index, DigitsCount, Size, Digits, 0).

nth_permutation(Index, _, 1, Digits, Acc) ->
    Last = lists:nth(Index+1, Digits),
    {10*Acc + Last, lists:delete(Last, Digits)}; 
nth_permutation(Index, DigitsCount, Size, Digits, Acc) ->
    NextCount = count(DigitsCount - 1, Size - 1),
    DigitIndex = (Index div NextCount) + 1,
    NextDigit = lists:nth(DigitIndex, Digits),
    nth_permutation(Index rem NextCount, DigitsCount - 1, Size - 1, lists:delete(NextDigit, Digits), 10*Acc + NextDigit).

number_to_digits(X) ->
    number_to_digits(X, []).

number_to_digits(0, Acc) ->
    Acc;
number_to_digits(X, Acc) ->
    number_to_digits(X div 10, [X rem 10|Acc]).

digits_to_number(Digits) -> 
    digits_to_number(Digits, 0).    
digits_to_number([], Acc) -> Acc;    
digits_to_number([H|Digits], Acc) ->
    digits_to_number(Digits, Acc*10 + H).
